<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    const arr = [1, 4, 3, 5, 5, 9, 2]

    // 冒泡排序
    function bubbleSort(arr) {
      const len = arr.length

      for (let i = 0; i < len; i++) {
        let flag = false
        for (let j = 0; j < len - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            flag = true
          }
        }
        if (!flag) {
          return arr
        }
      }
      return arr
    }
    console.log(bubbleSort(arr));

    // 选择排序
    function selectSort(arr) {
      const len = arr.length

      for (let i = 0; i < len - 1; i++) {
        let minIndex = i
        for (let j = i + 1; j < len; j++) {
          if (arr[j] < arr[minIndex]) {
            minIndex = j
          }
        }
        if (minIndex !== i) {
          [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
        }
      }
      return arr
    }
    console.log(selectSort(arr));

    // 插入排序
    function insertSort(arr) {
      const len = arr.length

      for (let i = 1; i < len; i++) {
        let j = i
        let temp = arr[i]
        while (j > 0 && arr[j - 1] > temp) {
          arr[j] = arr[j - 1]
          j--
        }
        arr[j] = temp
      }
      return arr
    }

    console.log(insertSort(arr));






    // 归并排序
    function mergeSort(arr) {
      const len = arr.length
      if (len <= 1) {
        return arr
      }

      let mid = Math.floor(len / 2)

      let leftArr = mergeSort(arr.slice(0, mid))
      let rightArr = mergeSort(arr.slice(mid, len))

      return mergeArr(leftArr, rightArr)
    }

    function mergeArr(leftArr, rightArr) {
      const len1 = leftArr.length
      const len2 = rightArr.length
      let res = []
      let i = 0, j = 0
      while (i < len1 && j < len2) {
        if (leftArr[i] <= rightArr[j]) {
          res.push(leftArr[i])
          i++
        } else {
          res.push(rightArr[j])
          j++
        }
      }

      if (i < len1) {
        return res.concat(leftArr.slice(i))
      } else {
        return res.concat(rightArr.slice(j))
      }
    }
    console.log(mergeSort(arr));

    // 快速排序
    function quickSort(arr) {
      if (arr.length < 2) {
        return
      }
      process1(arr, 0, arr.length - 1)
      return arr
    }

    function process1(arr, l, r) {
      if (l >= r) {
        return
      }
      let m = partition(arr, l, r)
      process1(arr, l, m - 1)
      process1(arr, m + 1, r)
    }

    function partition(arr, l, r) {
      if (l > r) {
        return -1
      }
      if (l === r) {
        return l
      }

      let lessEqual = l - 1
      let index = l
      while (index < r) {
        if (arr[index] <= arr[r]) {
          lessEqual++
          [arr[index], arr[lessEqual]] = [arr[lessEqual], arr[index]]
        }
        index++
      }
      lessEqual++
      [arr[lessEqual], arr[r]] = [arr[r], arr[lessEqual]]
      return lessEqual
    }

    console.log(quickSort(arr));
  </script>
</body>

</html>